package leetcode_day._2021._202105._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/8 18:24
 * 完成所有工作的最短时间
 * 回溯
 * 剪枝：只是调整了遍历的顺序，让不满足最优条件的分支提前结束, 并不是从根开始剪
 * 加入 used 后，剪枝增强了，第二次执行的时候，如果 max 还比 ans 大，那么表示工作分配没有前一次好
 */
public class _08_1723 {
    public static void main(String[] args) {
        System.out.println(new _08_1723().minimumTimeRequired(new int[]{19,12,10}, 2));
    }

    int ans = Integer.MAX_VALUE;
    public int minimumTimeRequired(int[] jobs, int k) {
        int[] sum = new int[k];
        dfs(jobs, sum, 0, 0, 0);
        return ans;
    }
    public void dfs(int[] jobs, int[] sum, int max, int used, int cur) {
        if (max >= ans) return;
        if (cur == jobs.length) {
            ans = max;
            return;
        }
        if (used < sum.length) {
            sum[used] = jobs[cur];
            dfs(jobs, sum, max > sum[used] ? max : sum[used], used + 1, cur + 1);
            sum[used] = 0;
        }
        // 这里如果为 i < sum.length, 就会重复计算一次
        // 当执行了 sum[used] = 0, 后面循环时, sum[used] 在被赋值的情况下，而且 used < sum.length，所以会执行 if 语句里的
        // 内容，这是 sum[used] = jobs[cur]，这样原来的值就被覆盖了，sum 从 [19, 12]，变成了 [19, 10]，然后 cur = jobs.length
        // 这时会使 ans = 19, 就错了, 因为最大值不可能为 19，这里还有个 22，而 12 被吞了
        for (int i = 0; i < used; i++) {
            sum[i] += jobs[cur];
            dfs(jobs, sum, max > sum[i] ? max : sum[i], used, cur + 1);
            sum[i] -= jobs[cur];
        }
    }

}
